Network interconnection devices, such as routers, switches, gateways and concentrators, etc., include input and output ports that respectively receive and retransmit data. Generally, these devices include multiple input and multiple output ports, and the ports may be coupled to similar or dissimilar networks. The function of a network interconnection device is to receive packets on an input port, examine each packet to determine its destination address, and then forward the packet to the output port most likely to ensure the packet's delivery to its destination. The network device temporarily stores the input packets while the device determines the correct output port and outputs the data on that port.
Packets arrive at the input ports of the network device at random time intervals, although an approximate average arrival rate is generally known. For example, at one input port two thousand packets could arrive every second for five seconds, and at another input port eight thousand packets could arrive in the first second and another two thousand packets four seconds later. The average packet receive rate is 2 thousand packets/second in both of these cases. Generally, the packets do not arrive at exact intervals like in the first example; instead, packets are more likely to arrive in a distribution as in the second example. Sometimes this distribution is called data bursting.
In order to keep up with the incoming bursting packet traffic, the network device stores the incoming packets as they enter the input ports prior to sending them out to the output port. Present devices temporarily store incoming packets in data buffers or FIFO (First-In, First-Out) queues until they are ready to be forwarded to the proper output port or ports. For multicast traffic, if the network device cannot service the packets in an allotted time period, the device rejects (or drops) the unserviceable packets. For unicast traffic, if the Virtual Output Queue (VOQ) is congested, the packets will be rejected (or dropped). Packet processing speed in a network device is limited by the amount of time required to read and write packets to and from memory buffers. As network traffic increases and router specifications require more data throughput, packets must be forwarded at much faster rates than the present rates while having the same or lower packet drop rates. Memory read and rewrite bottlenecks prevent the network device from processing packets at the highest packet rates.
The present invention addresses this and other problems associated with the prior art.